package _01_sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author: mornd
 * @dateTime: 2023/6/23 - 9:37
 * 计数排序 (前提是数组元素必须都>=0)
 * 1、找到最大值，创建一个大小为最大值 +1 的新数组
 * 2、新数组的索引对应原始数组的元素，索引值对应元素出现的次数
 * 3、遍历新数组，根据新数组的索引以及索引值(出现次数)，生成排序好的内容
 */
public class CountingSort {
    @Test
    public void test() {
        int[] arr = {4, 3, 1, 5, 6, 3};
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private void countingSort(int[] arr) {
        //  1、找到数组最大元素
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max = Math.max(arr[i], max);
        }
        // 新建数组记录出现元素的个数
        int[] countArr = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
        }
        // 3、根据新数组的索引及索引值，组成有序的数组
        for (int i = 0, j = 0; i < countArr.length; i++) {
            int c = countArr[i];
            while (c > 0) {
                arr[j++] = i;
                c--;
            }
        }
    }
}
